package com.yangli.leecode.mashib.interview;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/14 13:12
 */
public class Fifty {
    public static void main(String[] args){
        System.out.println(Fifty.lengthOfLongestSubStringKDistinct("aaaabbbccccccddddd", 2));
        System.out.println(Fifty.kth("ba", 2));

    }

    //0279
    //四平方和定义:一个正整数最多表示为四个正整数的和。 n = (4^a)*(8b+7) 满足这个公式则表示完全平方数是4个。
    //然后判断 i * i + j * j == n条件，否则就是三个数
    public int numSquares(int n){
        while (n % 4 == 0) {
            n /= 4;
        }
        if (n % 8 == 7) {
            return 4;
        }
        for (int i = 0; i < n; i++) {
            int j = (int) Math.sqrt(n - i * i);
            if (i * i + j * j == n) {
                return (i > 0 && j > 0 ? 2 : 1);
            }
        }
        return 3;
    }

    //0289
    public void gameOfLife(int[][] board){
        int n = board.length;
        int m = board[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int count = liveCount(board, i, j);
                if (count == 3 || (board[i][j] == 1 && count == 2)) {
                    board[i][j] |= 2;//存活/死亡3个，或者存活且2个，下次变化为1，用int位信息表示
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] >>= 1;
            }
        }
    }

    //查找8的邻居上的存活数量
    private int liveCount(int[][] board, int i, int j){
        return liveCondition(board, i - 1, j - 1) +
                liveCondition(board, i - 1, j) +
                liveCondition(board, i - 1, j + 1) +
                liveCondition(board, i, j - 1) +
                liveCondition(board, i, j + 1) +
                liveCondition(board, i + 1, j - 1) +
                liveCondition(board, i + 1, j) +
                liveCondition(board, i + 1, j + 1);
    }

    private int liveCondition(int[][] board, int i, int j){
        return (i >= 0 && i < board.length && j >= 0 && j < board[0].length && (board[i][j] & 1) == 1) ? 1 : 0;
    }

    //0326
    public boolean isPowerOfThree(int n){
        return n > 0 && 1162261467 % n == 0;
    }

    //0340
    public static int lengthOfLongestSubStringKDistinct(String s, int k){
        if (s == null || s.length() == 0 || k < 1) {
            return 0;
        }
        int l = 0;
        int r = 0;
        int n = s.length();
        int ans = 0;
        int distinct = 0;
        int[] count = new int[26];
        while (l <= r && r < n) {
            if (distinct <= k) {
                int index = s.charAt(r++) - 'a';
                if (count[index] == 0) {
                    distinct++;
                }
                count[index]++;
                ans = Math.max(ans, r - l);
            } else {
                int index = s.charAt(l++) - 'a';
                if (count[index] == 1) {
                    distinct--;
                }
                count[index]--;
            }
        }
        return ans;
    }

    //
    public static int kth(String s, int k){
        if (s == null || s.length() == 0 || k < 1) {
            return -1;
        }
        int ans = 1;
        for (int i = 0, rest = k - 1; i < s.length(); i++, rest--) {
            ans += (s.charAt(i) - 'a') * kthFunction(rest) ;
        }
        return ans;
    }

    //不管以什么开头，剩下长度0-len的所有可能性
    public static int kthFunction(int len){
        int ans = 1;
        for (int i = 1, base = 26; i <= len; i++, base *= 26) {
            ans += base;
        }
        return ans;
    }
}
